// Copyright (C) 2010 and onwards Noam Shazeer and Georges Harik
// Pieces of this code may be licenced under the Apache License, version 2.0 
//   from Harik Shazeer Labs

#include <sstream>
#include <fstream>
#include <string.h>
#include <limits.h>
#include "shorthand.h"
#include "interpret.h"
#include "util.h"
#include "jobqueue.h"
#include "setval.h"
#include "lexicon.h"
#include "objects.h"
#include "hashthing.h"

map<int , string> Vinterpreter::op_string_;

// constants for the interpreter
int32 kStackSizeWords = (int32)20e6;
int32 kDebugStackSize = (int32) 1e6;
int32 kCodeStackSize = (int32) 1e6;
int32 kHandlerStackSize = (int32) 1e5;
int64 kInterpretCacheSize = (1 << 22); 
uint64 kArrayStackSize = (1 << 23);
uint64 kCompileSize = (uint64)1e7;
uint64 kCompileLogSize = (uint64) 1e7;
uint64 kLocalsSize = (uint64) 1e3;
int64 kInliningDepth = 0;

// Lock for printing
pthread_mutex_t PRINT_LOCK;

GlobalInterpreter * G_INTERP;

#define _NATIVE(name) Thing name;
#define _NATIVE2(cname, lispname) Thing cname;
ALL_NATIVES
#undef _NATIVE
#undef _NATIVE2

#define _SPECIAL(name) Thing name;
ALL_SPECIAL
#undef _SPECIAL

vector<uint64> G_SYSCALL_PERMISSIONS;

void SetSyscallPermissions(uint64 call, uint64 permissions) {
  while (G_SYSCALL_PERMISSIONS.size() <= call) 
    G_SYSCALL_PERMISSIONS.push_back(0);
  G_SYSCALL_PERMISSIONS[call] = permissions;
}
bool SyscallPermitted(uint64 call, uint64 mode) { 
  if (call >= G_SYSCALL_PERMISSIONS.size()) return false;
  return G_SYSCALL_PERMISSIONS[call] & mode; 
}

void InitUnboxedThings() {
#define _NATIVE2(cname, lispname)					\
  cname = Thing::BindUnboxed(NATIVE_FUNCTION, NATIVE_##cname, #lispname);
#define _NATIVE(name)							\
  name = Thing::BindUnboxed(NATIVE_FUNCTION, NATIVE_##name, #name);
  ALL_NATIVES;
#undef _NATIVE
#undef _NATIVE2
  
#define _SPECIAL(name) name = Thing::BindUnboxed(SPECIAL, SPECIAL_##name, #name);
  ALL_SPECIAL;
#undef _SPECIAL

  // define all syscalls here. 
  uint64 a = kEconomyMode | kGenerativeMode;
  uint64 g = kGenerativeMode;
  uint64 e = kEconomyMode;
  
  // bind all syscalls
#define _SYSCALL(name, permissions)				\
  name = Thing::BindUnboxed(SYSCALL, SYSCALL_##name, #name);	\
  SetSyscallPermissions(SYSCALL_##name, permissions);
  ALL_SYSCALLS
#undef _SYSCALL

    // bind all the ops
#define _OP(name) Vinterpreter::op_string_[name] = #name;
    ALL_OPS
#undef _OP
    
}

Thing CStringToThingString(ThreadAllocator *a, char * cstr) {
  const uint64 limit = 1000;
  uint64 len = strlen(cstr);
  if (len > limit) return NIL;
  Thing char_things[limit];
  for (uint64 i = 0; i<len; i++)
    char_things[i] = Thing::MakeCharacter(cstr[i]);
  return a->MakeImmutableArray(LOCAL_ALLOCATION, &(char_things[0]), len);
}

Thing ToThing(ThreadAllocator *a_, string s) {
  istringstream i(s);
  return ReadThing(a_, i);
}

ostream & operator << (ostream & ostr, Thing p) {
  InitInterpret();
  if (p.IsNot()) {
    ostr << "null";
    return ostr;
  }
  switch(p.GetType()) {
  case CHAR: {
    unsigned char c = p.GetChar();
    if (c >= 33 && c <127) {
      ostr << "#" << p.GetChar();
      break;
    }
    ostr << "#" << hex << (c/16) << (c%16) << dec;
    break;
  }
  case TOKEN: 
    ostr << "." << G_LEXICON->IDToString(p.GetUnboxedValue()) << ".";
    break;
  case INTEGER:
    ostr << p.GetInteger();
    break;
  case DOUBLE:
    ostr << '_';
    ostr.precision(std::numeric_limits<double>::digits10 + 3);
    ostr << p.GetDouble();
    break;
    // TODO: verify this is reversible.
  case MUTABLE_ARRAY:
  case IMMUTABLE_ARRAY: {
    Box * b = p.MaybeGetBox();
    if (!b) {
      ostr << "[ERROR Boxless Array]";
      break;
    }
    uint64 node_count = p.NodeCount();
    CHECK(node_count > 0);
    CHECK(node_count < 1000000);
    if (b->ArraySize() == 2) {
      if (b->Ref(0) == QUOTE) {
	ostr << "\'";
	ostr << b->Ref(1);
	break;
      }
      if (b->Ref(0) == BACKQUOTE) {
	ostr << "`";
	ostr << b->Ref(1);
	break;
      }
      if (b->Ref(0) == COMMA) {
	ostr << ",";
	ostr << b->Ref(1);
	break;
      }
    }
    {
      bool is_string = true;
      for (uint64 i=0; i<b->ArraySize(); i++) {
	if (b->Ref(i).GetType() != CHAR) {
	  is_string = false;
	  break;
	}
      }
      if (b->ArraySize() == 0) is_string = false;
      if (is_string) {
	ostr << "\"";
	for (uint64 i=0; i<b->ArraySize(); i++) {
	  unsigned char c = b->Ref(i).GetChar();
	  if ( c == '"' || c == '#'  
	       || c < 32 || c > 126) 
	    ostr << '#' << hex << (c/16) << (c%16) << dec;
	else ostr << c;
	}
	ostr << "\"";
	break;
      }
    }
    // this prints arrays
    // ostr << "[" << (int)b->LgAccessCountRef() << "]";
    ostr << "(";
    if (b->IsMutable()) ostr << " ";
    for (uint64 i=0; i<b->ArraySize(); i++) {
      if (i != 0) ostr << " ";
      if (b->Ref(i) == p) { 
	ostr << "__loop_thing__"; 
      } else ostr << b->Ref(i);
    }
    ostr << ")";
    break;
  }
  case SYMBOL: {
    Box * b = p.MaybeGetBox();
    if (!b) {
      ostr << "[ERROR Boxless Symbol]";
      break;
    }
    for (uint64 i=0; i<b->ArraySize(); i++) {
      ostr << b->Ref(i).GetChar();
    }
    break;
  }
  default:
    string *s = Thing::thing_string_ % p;
    if (s) ostr << *s;
    else {
      ostr << "__unidentified_thing__ " 
	   << (void*)(p.data_) << endl;
    }
    break;
  }
  return ostr;
}

string ReadToken(istream& input) {
  InitInterpret();
  // Get rid of whitespace and test for EOF
  input >> ws;
  if (input.eof()) return "";

  char c;
  if (!input.get(c)) return "";

  // Single letter tokens
  switch (c) {
  case '(': return "(";
  case ')': return ")";
  case '{': return "{";
  case '}': return "}";
  case '\'': return "'";
  case '`': return "`";
  case ',': return ",";
  default:
    ;
  }
  if (c == '"') {
    string ret = "\"";
    input.get(c);
    while (c != '"') {
      ret += c;
      input.get(c);
    }
    ret += c;
    return ret;
  }

  if (c == '.') {
    string ret = ".";
    input.get(c);
    // Read tokens consisting of all .s
    if (c == '.') {
      ret += c;
      while (input.peek() == '.') {
	input.get(c);
	ret += c;
      }
      return ret;
    }
    while (c != '.') {
      ret += c;
      input.get(c);
    }
    ret += c;
    return ret;
  }
  
  // Handle comments
  if (c == '/') {
    if (input.peek() == '/') {
      while (!input.eof())
	if (input.get() == '\n') break;
      return ReadToken(input);
    }
    if (input.peek() == '*') {
      while (!input.eof())
	if (input.get() == '*' && input.peek() == '/') {
	  input.get();
	  break;
	}
      return ReadToken(input);  
    }
  }

  // Read up until whitespace or ')'
  string ret = "";
  ret += c;
  if (c == '#') ret += input.get(); // interpret #} and #) correctly. 
  while (input.peek() != ')' && input.peek() != '}' && !isspace(input.peek())) {
    if (!input.get(c)) break;
    ret += c;
  }

  // Special objects in the tokenizer
  if (ret == "/eof") return "";
 
  // cout << "Tokenizer about to return " << ret << "---" << endl;
  return UpperCase(ret);
}

Thing ReadThing(ThreadAllocator *a_, istream &input) {
  string tok = ReadToken(input);
  Thing ret;

  // Detect end of tokenization
  if (tok == "") return NULL;
  
  // We use this to close off array things
  if (tok == ")") return NULL;
  if (tok == "}") return NULL;
  
  // Read things until you see ')' which returns a NULL
  if (tok == "(") {
    vector<Thing> v;
    while (1) {
      Thing s = ReadThing(a_, input);
      if (s.IsNot()) break;
      v.push_back(s);
    }
    return a_->MakeImmutableArray(GLOBAL_ALLOCATION, v);
  } 
  if (tok == "'") {
    Thing inner = ReadThing(a_, input);
    return a_->MakeImmutableArray2(GLOBAL_ALLOCATION, QUOTE, inner);}

  if (tok == ",") {
    Thing inner = ReadThing(a_, input);
    return a_->MakeImmutableArray2(GLOBAL_ALLOCATION, COMMA, inner); }

  if (tok == "`") {
    Thing inner = ReadThing(a_, input);
    return a_->MakeImmutableArray2(GLOBAL_ALLOCATION, BACKQUOTE, inner); }

  if (tok[0] == '_') {
    double d = atof(tok.c_str() + 1);
    Thing ret = Thing::MakeDouble(d);
    return ret;
  }

  // Integers
  if (isdigit(tok[0]) || 
      ((tok.length() > 1) && (isdigit(tok[1])) && (tok[0] == '-'))) {
    int64 ll_value = atoll(tok.c_str());
    Thing ret = Thing::MakeInteger(ll_value);
    ostringstream reout;
    reout << ret.GetInteger();
    if (reout.str() == tok) 
      return ret;
    return ERROR;
  }

  // characters
  if (tok[0] == '#') {
    if (tok.size() == 2) return Thing::MakeCharacter(tok[1]);
    if (tok.size() != 3) return ERROR;
    return Thing::MakeCharacter(HexToInt(tok.substr(1)));
  }

  // strings
  if (tok[0] == '"') {
    vector<Thing > v;
    for (uint32 i=1; i+1<tok.size(); i++) {
      unsigned char c = tok[i];
      if (c == '#') {
	c = HexToInt(tok.substr(i+1, 2));
	i+=2;
      }
      v.push_back(Thing::MakeCharacter(c));
    }
    return a_->MakeImmutableArray(GLOBAL_ALLOCATION, v);
  }

  // Lexicon token
  if (tok[0] == '.') {
    tok.resize(tok.size() - 1); // Read tokens correctly
    return Thing::MakeToken(G_LEXICON->StringToID(tok.c_str() + 1)); 
  }

  // Token could be an unboxed named object
  Thing ubno = Thing::NameToUnboxedThing(tok);
  if (ubno.Is()) return ubno;
  
  return a_->MakeSymbol(tok);
}

// returns the thing itself if it just needs to be quoted, otherwise returns
// the correct expanded backquote
// Assumes that root is already protected from garbage collection
Thing ExpandBackquoteInternal(ThreadAllocator *a_, Thing root) {
  if (!root.IsArray()) return root;
  Box * rootb = root.GetBox();
  int size = rootb->ArraySize();
  if ( (size == 2) && (rootb->Ref(0) == COMMA)) return rootb->Ref(1);
  vector<Thing> tmp;
  tmp.push_back(ARRAY);
  bool all_same = true;
  for (int i=0; i<size; i++) {
    tmp.push_back(ExpandBackquoteInternal(a_, rootb->Ref(i)));
    if (tmp.back() != rootb->Ref(i)) all_same = false;
  }
  if (!all_same) { 
    for (int i=0; i<size; i++) {
      if (tmp[i+1] == rootb->Ref(i)) {
	Thing sub = tmp[i+1];
	tmp[i+1] = a_->MakeImmutableArray2(LOCAL_ALLOCATION, QUOTE, sub);
      }
    }
    return a_->MakeImmutableArray(LOCAL_ALLOCATION, tmp);
  }
  return root;
}

Thing ExpandBackquote(ThreadAllocator *a_, Thing root) {
  Thing ret = ExpandBackquoteInternal(a_, root);
  if (ret == root) return a_->MakeImmutableArray2(LOCAL_ALLOCATION, 
						  QUOTE, root);
  // cout << "Expanding backquote " << ToString(root) << " returns " << ToString(ret) << endl;
  return ret;
}

void InitInterpret() {
  static int done = 0; if (done++) return;
  kInliningDepth = ConfigInt("inlining_depth");
  InitTimer();
  InitMath();
  InitAllocator();
  InitUnboxedThings();
  InitObjects();
  G_INTERP = new GlobalInterpreter();
  pthread_mutex_init(&PRINT_LOCK, NULL);
  // cout << "InitInterpret::\n";
}

Thing Vinterpreter::StackTopToArray(int32 n) {
  for (int32 i=0; i<n; i++) if (stack_top_[i-n].IsMutable()) return NULL;
  return a_->MakeImmutableArray(LOCAL_ALLOCATION, 
				stack_top_-n, n);
}
Thing Vinterpreter::StackTopToMArray(int32 n) {
  return a_->MakeMutableArray(stack_top_-n, n);
}

Thing Vinterpreter::LambdadCode(Thing & code) {
  Thing zero = a_->MakeImmutableArray0(LOCAL_ALLOCATION);
  return a_->MakeImmutableArray3(LOCAL_ALLOCATION, LAMBDA, zero, code);
}

Thing Vinterpreter::EvaledCode(Thing & code) {
  Thing la_code = LambdadCode(code);
  return a_->MakeImmutableArray1(LOCAL_ALLOCATION, la_code);
}

CompileLogger::CompileLogger(Vinterpreter * v, Thing code) 
  : v_(v), code_(code) {
  v_->compile_log_.push_back(Thing::MakeInteger(COMPILE_ENTER));
  v_->compile_log_.push_back(code);
  v_->compile_log_.push_back(Thing::MakeInteger(v_->compile_.size()));
}

CompileLogger::~CompileLogger() {
  v_->compile_log_.push_back(Thing::MakeInteger(COMPILE_EXIT));
  v_->compile_log_.push_back(code_);
  v_->compile_log_.push_back(Thing::MakeInteger(v_->compile_.size()));
}

Vinterpreter::Vinterpreter()
  :array_stack_(kArrayStackSize),
   compile_(kCompileSize),
   compile_log_(kCompileLogSize),   
   locals_(kLocalsSize)
{
  compile_depth_ = 0;
  array_stack_.descriptor_ = "array_stack_";
  compile_.descriptor_ = "compile_";
  compile_log_.descriptor_ = "compile_log_";
  locals_.descriptor_ = "locals_";
  a_ = NULL;
  int stack_size = kStackSizeWords;
  int debug_stack_size = kDebugStackSize;
  int code_stack_size = kCodeStackSize;
  int handler_stack_size = kHandlerStackSize;
  stack_ = new Thing[stack_size];
  stack_top_ = stack_;
  stack_limit_ = stack_ + stack_size;
  debug_stack_ = new Thing[debug_stack_size];
  debug_stack_top_ = debug_stack_;
  debug_stack_limit_ = debug_stack_ + debug_stack_size;
  // Set up the code stack
  code_stack_ = new CodeStackFrame[code_stack_size];
  code_stack_top_ = code_stack_;
  code_stack_limit_ = code_stack_ + code_stack_size;
    // Set up the limit stack
  handler_stack_ = new HandlerFrame[handler_stack_size];
  handler_stack_top_ = handler_stack_;
  handler_stack_limit_ = handler_stack_ + handler_stack_size;
  debug_level_ = 0;
  system_ = NULL;
  ip_ = 0;
  function_uncachable_count_ = 0;
  program_uncachable_count_ = 0;
  clock_check_ = 0;
  ClearStacks();
}

void Vinterpreter::Display() {
  cout << "--- Stack ---" << endl;
  for (Thing * run = stack_; run < stack_top_; run++) 
    cout << *run << endl;
  cout << "--- END Stack ---" << endl;
}

#define NEXT_INSTRUCTION goto *jmparray[(*ip_).GetInteger()]

/*
#define NEXT_INSTRUCTION { int64 op = ip_->GetInteger(); \
  cout << "op: " << op_string_[op] << endl; \
goto *jmparray[(*ip_).GetInteger()]; }
*/

#define INTERPRET_THROW(x) \
  { Throw(x, string(__FILE__) + ":" + itoa(__LINE__)); \
    if (safe_execute_die_) return NULL; \
    continue; }

#define INTERPRET_THROW_RETURN(x) \
  { Throw(x, string(__FILE__) + ":" + itoa(__LINE__)); \
    return; }


#define _OP(name) &&name##_label,

Thing Vinterpreter::Execute(const Thing * ip_in) {

  static void *jmparray[] = {
    ALL_OPS
  };

  JumpTo(ip_in);

  while (1) {
    NEXT_INSTRUCTION;

  PRINT_OP_label: {
      ip_++;
      NoFunctionCache();
      // Not NoProgramCache so we can put Prints in generative code
      pthread_mutex_lock(&PRINT_LOCK);
      cout << stack_top_[-1] << endl;
      pthread_mutex_unlock(&PRINT_LOCK);
      continue;
    }
    
  PRINT_STRING_OP_label: {
      ip_++;
      NoFunctionCache();
      // Not NoProgramCache so we can put Prints in generative code
      Thing s = stack_top_[-1];
      if (!s.IsString()) INTERPRET_THROW(TYPE_EXCEPTION);
      pthread_mutex_lock(&PRINT_LOCK);
      for (uint64 i=0; i<s.ArraySize(); i++)
	cout << s.Ref(i).GetChar();
      pthread_mutex_unlock(&PRINT_LOCK);
      continue;
    }

  PUSH_THING_OP_label: {
    ip_++; 
    *stack_top_ = *ip_; 
    stack_top_++;
    ip_++;
    continue;
  }

  POP_OP_label: {
    ip_++; 
    stack_top_--;
    continue;
    }
    
  TO_INT_OP_label: {
    ip_++;
    Thing ret = ThingToIntThing(stack_top_[-1]);
    if (ret.IsNot()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_[-1] = ret;
    continue;
    }

  TO_DOUBLE_OP_label: {
    ip_++;
    Thing ret = ThingToDoubleThing(stack_top_[-1]);
    if (ret.IsNot()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_[-1] = ret;
    continue;
    }

  INT_CHAR_OP_label: {
    ip_++;
    if (!(stack_top_[-1].IsInteger())) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_[-1] = Thing::MakeCharacter(stack_top_[-1].GetInteger());
    continue;
    }

  PLUS_OP_label: {
    ip_++;
    Thing result = ThingPlus(stack_top_[-2], stack_top_[-1]);
    if (result.IsNot()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_-= 1;
    stack_top_[-1] = result;
    continue;
    }

  TIMES_OP_label: {
    ip_++;
    Thing result = ThingTimes(stack_top_[-2], stack_top_[-1]);
    if (result.IsNot()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_-= 1;
    stack_top_[-1] = result;
    continue;
    }
    
  CONST_PLUS_OP_label: {
    ip_++;
    Thing result = ThingPlus(stack_top_[-1], *ip_);
    ip_++;
    if (result.IsNot()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_[-1] = result;
    continue;
    }

  CONST_TIMES_OP_label: {
    ip_++;
    Thing result = ThingTimes(stack_top_[-1], *ip_);
    ip_++;
    if (result.IsNot()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_[-1] = result;
    continue;
    }

  CONST_EQUAL_OP_label: {
    ip_++;
    stack_top_[-1] = (stack_top_[-1] == *ip_) ? T : NIL;
    ip_++;
    continue;
    }

  MOD_OP_label: {
    ip_++;
    if (stack_top_[-1].IsInteger() &&
	stack_top_[-2].IsInteger()) {
      int64 n1 = stack_top_[-2].GetInteger();
      int64 n2 = stack_top_[-1].GetInteger();
      if (n2 == 0) INTERPRET_THROW(ARITHMETIC_EXCEPTION);
      int64 int64_res = n1 % n2;
      stack_top_ -= 1;
      stack_top_[-1] = Thing::MakeInteger(int64_res);
      continue;
    }
    INTERPRET_THROW(TYPE_EXCEPTION);
    }

  DIVIDE_OP_label: {
    ip_++;
    if (stack_top_[-1] == Thing::MakeInteger(0))
      INTERPRET_THROW(ARITHMETIC_EXCEPTION);
    Thing result = ThingDivide(stack_top_[-2], stack_top_[-1]);
    if (result.IsNot()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_-= 1;
    stack_top_[-1] = result;
    continue;
    }    
    
  MINUS_OP_label: {
    ip_++;
    Thing result = ThingMinus(stack_top_[-2], stack_top_[-1]);
    if (result.IsNot()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_-= 1;
    stack_top_[-1] = result;
    continue;
    }

  EQUAL_OP_label:
    {
      ip_++;
      Thing ret = (stack_top_[-1] == stack_top_[-2]) ? T : NIL;
      stack_top_ -= 1;
      stack_top_[-1] = ret;
      continue;
    }

  LESS_THAN_OP_label: {
    ip_++;
    Thing result = ThingLessThan(stack_top_[-2], stack_top_[-1]);
    if (result.IsNot()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_-= 1;
    stack_top_[-1] = result;
    continue;
    }

  NOT_OP_label: {
    ip_++ ; 
    stack_top_[-1] = (stack_top_[-1] == NIL) ? T : NIL;
    continue;
    }

  TOSTRING_OP_label: 
    {
      string c_string = ToString(stack_top_[-1]);
      uint64 length = c_string.size();
      uint64 i = 0;
      if (array_stack_.size() + length > array_stack_.capacity_) {
	INTERPRET_THROW(UNKNOWN_EXCEPTION);
      }
      for (i=0; i<length; i++)
	array_stack_.push_back(Thing::MakeCharacter(c_string[i]));
      stack_top_[-1] = 
	a_->MakeImmutableArray(LOCAL_ALLOCATION, 
			       array_stack_.current_ - length, length);
      array_stack_.current_ -= length;
      ip_++;
      continue; // continue;
    }

  TOSYMBOL_OP_label:
    {
      string c_string = StringToCPPString(stack_top_[-1]);
      Thing result = NIL;
      if (c_string == "") {
	INTERPRET_THROW(UNKNOWN_EXCEPTION);
      }
      result = a_->MakeSymbol(c_string);
      if (result.IsNot()) {
	INTERPRET_THROW(UNKNOWN_EXCEPTION);
      }
      stack_top_[-1] = result;
      ip_++;
      continue; // continue;
    }

  S_OP_label: {
    int64 constant_pos = ip_[1].GetInteger();
    //cout << "constant_pos = " << constant_pos << endl;
    //cout << "1 sop stack_top_ " << stack_top_ << endl;
    //cout << "1 sop value = " << stack_top_[-1] << endl;
    *stack_top_ = stack_top_[constant_pos];
    stack_top_++;
    //cout << "2 sop stack_top_ " << stack_top_ << endl;
    //cout << "2 sop value = " << stack_top_[-1] << endl;
  ip_ += 2;
    continue;
    }

  DEBUG_VAR_INTRO_OP_label: 
    {
      ip_++;
      Thing var = *ip_;
      ip_++;
      Thing offset = *ip_;
      int64 i_offset = offset.GetInteger();
      CHECK(var.IsSymbol());
      if (debug_stack_top_ == debug_stack_limit_) {
	INTERPRET_THROW(STACK_EXCEPTION);
      }
      *(debug_stack_top_++) = var;
      *(debug_stack_top_++) = 
	Thing::MakeInteger(stack_top_ - 1 - stack_ + i_offset);
      ip_++;
      continue;
    }
    
  DEBUG_VAR_REMOVE_OP_label: {
      ip_++;
      int64 num_vars = ip_->GetInteger();
      debug_stack_top_ -= 2 * num_vars;
      CHECK(debug_stack_top_ >= debug_stack_);
      ip_++;
      continue;
    }
    
  JUMP_OP_label: {
    ip_++;
    JumpBy(ip_->GetInteger());
    continue;
    }
    
  TEST_JUMP_OP_label: {
      bool jumping = (stack_top_[-1] == NIL);
      stack_top_--;
      if (jumping) {
	ip_++;
	JumpBy(ip_->GetInteger());
	continue;
      }
      ip_ += 2;
      continue;    
    }

  AND_OP_label: {// if top thing is nil, jump to given location
    bool jumping = (stack_top_[-1] == NIL);
    if (jumping) {
      ip_++;
      JumpBy(ip_->GetInteger());
      continue;
    }
    ip_ += 2;
    continue;
    }

  OR_OP_label: {
    bool jumping = !(stack_top_[-1] == NIL);
    if (jumping) {
      ip_++;
      JumpBy(ip_->GetInteger());
      continue;
    }
    ip_ += 2;
    continue;
    }
    
  PUSH_HANDLER_OP_label: {
    // Add a frame to the limit stack
    if (handler_stack_top_ == handler_stack_limit_) INTERPRET_THROW(UNKNOWN_EXCEPTION);
    ip_++;
    Thing handler_type = *ip_;
    ip_++;
    int64 handler_jump = ip_->GetInteger();
    Thing handler_arg = stack_top_[-1];
    stack_top_--;
    int64 limit_int = handler_stack_top_[-1].clock_limit_;
    Thing exceptions = NIL;
    if (handler_type == LIMIT) {
      bool has_limit = handler_arg.IsInteger();
      if (!has_limit) INTERPRET_THROW(TYPE_EXCEPTION);
      int64 clock1 = clock_.Get();
      int64 asked_limit = handler_arg.GetInteger();
      if (asked_limit < 1000) asked_limit = 1000;
      if (asked_limit + clock1 < clock1) INTERPRET_THROW(UNKNOWN_EXCEPTION);
      limit_int = min(limit_int, asked_limit + clock1);
      CHECK(limit_int >= 0);      
    } else {
      exceptions = handler_arg;
    }
    ip_ += handler_jump;
    PushHandlerFrame(limit_int, exceptions, handler_type);
    ip_ -= handler_jump;
    ip_++;
    continue;
    }

  CRASH_OP_label: {
    INTERPRET_THROW(UNKNOWN_EXCEPTION);
    }

  THROW_OP_label: {
    Thing throw_arg = stack_top_[-1];
    INTERPRET_THROW(throw_arg);
    }    

  RESIZE_OP_label: {
    Thing array = stack_top_[-2];
    if (!array.IsArray()) INTERPRET_THROW(TYPE_EXCEPTION);
    Box * arrayb = array.GetBox();
    if (!arrayb->IsMutable()) INTERPRET_THROW(TYPE_EXCEPTION);
    Thing new_size_t = stack_top_[-1];
    if (!new_size_t.IsInteger()) INTERPRET_THROW(TYPE_EXCEPTION);
    int64 new_size = new_size_t.GetInteger();
    int64 old_size = arrayb->GetLength();
    if (new_size < 0) INTERPRET_THROW(UNKNOWN_EXCEPTION);
    // may want to check time here. 
    a_->ResizeMutableArray(arrayb, new_size);
    arrayb = array.GetBox();
    for (int64 i = old_size; i < new_size; i++) arrayb->Ref(i) = NIL;
    stack_top_ -= 1;
    ip_++;
    continue;
    }

  RG_OP_label: {
      NoFunctionCache();
      ip_++;
      *stack_top_ = run_global_;
      stack_top_++;
      continue;
    }
      
  POP_HANDLER_OP_label: {
    ip_++;
    PopHandlerFrame();
    continue;
    }

  GETLIMIT_OP_label: {
      NoProgramCache();
      NoFunctionCache();
      ip_++;
      *stack_top_ = Thing::MakeInteger(TimeRemaining());
      stack_top_++;
      continue;
    }

  TIME_OP_label: {
    ip_++;
    *stack_top_ = Thing::MakeInteger(clock_.Get());
    stack_top_++;
    continue;    
    }

  FORGET_OP_label: {
    CHECK(false);
    /*
    ip_++;
    if (stack_top_[-1] == NIL) {
      // tell the system to forget everything that happened since stack_top_[-2]
      system_->ForgetSince(stack_top_[-2].GetInteger());      
    }
    stack_top_[-2] = stack_top_[-1];
    stack_top_--;
    continue;
    */
    }

  START_DOTIMES_OP_label: {
    Thing n = stack_top_[-1];
    if (!n.IsInteger()) INTERPRET_THROW(TYPE_EXCEPTION);
    int64 int_n = n.GetInteger();
    if (int_n<0) INTERPRET_THROW(UNKNOWN_EXCEPTION);
    ip_++;
    Thing op = *ip_;
    ip_++;
    int64 jump_by = ip_->GetInteger();
    *stack_top_ = op;
    stack_top_++;
    if (stack_top_[-1].IsNot()) INTERPRET_THROW(UNKNOWN_EXCEPTION);
    *stack_top_ = Thing::MakeInteger(-1);
    stack_top_++;
    *stack_top_ = NIL; // junk value
    stack_top_++;
    JumpBy(jump_by);
    
    continue; // may want to inline the jump?... 
    }

  NEXT_DOTIMES_OP_label: {
    ip_++;
    int64 jump_by = ip_->GetInteger();
    Thing result = stack_top_[-1];
    int32 i = stack_top_[-2].GetInteger();
    Thing op = stack_top_[-3];
    int32 n = stack_top_[-4].GetInteger();
    if ((i>=0) && (op == DOTIMES)) {
      if (result.IsMutable()) INTERPRET_THROW(TYPE_EXCEPTION);
      if (array_stack_.size() == array_stack_.capacity_)
	INTERPRET_THROW(UNKNOWN_EXCEPTION);
      array_stack_.push_back(result);
    }
    i++;
    stack_top_--;
    if (SometimesOvertime()) {
      FailTimeLimit();
      if (safe_execute_die_) return NULL;
      continue; 
    }
    
    Thing break_value = NULL;
    if (op == REPEAT) {
      if (result == BREAK) break_value = BREAK;
      else 
	if (result.IsArray() && 
	    (result.ArraySize() == 2) && 
	    (result.Ref(0) == BREAK))
	  break_value = result.Ref(1);
    }

    if ((i < n) && break_value.IsNot()) {
      stack_top_[-1] = Thing::MakeInteger(i);
      JumpBy(jump_by);      
      continue;
    }

    // return the array
    stack_top_[-3] = stack_top_[-2];
    stack_top_-=2;
    if (stack_top_[-1] == DOTIMES) {
      stack_top_[-1] = 
	a_->MakeImmutableArray(LOCAL_ALLOCATION, array_stack_.current_ - n, n);
      array_stack_.current_ -= n;
    } else {
      // REPEAT
      stack_top_[-1] = break_value.Is() ? break_value : NIL;
    }
    ip_++;
    continue;  
    }

  FUNCALL_OP_label: {
    ProcessFuncallOp(FUNCALL_OP); 
    if (safe_execute_die_) return NULL;
    continue;
    }

  APPLY_OP_label: {
    ProcessFuncallOp(APPLY_OP);
    if (safe_execute_die_) return NULL;
    continue;
    }

  SYSCALL_OP_label:
    {
      if (!system_) INTERPRET_THROW(UNKNOWN_EXCEPTION);
      ip_++;
      int32 syscall_value = ip_->GetInteger();
      ip_++;
      int32 num_params = ip_->GetInteger();
      if (!SyscallPermitted(syscall_value, mode_)) 
	INTERPRET_THROW(UNKNOWN_EXCEPTION);
      Thing syscall_return;
      try {
	syscall_return = system_->SystemCall(syscall_value, num_params);
      } catch (Thing x) {
	if (x == OVERTIME_EXCEPTION) {
	  FailTimeLimit();
	  if (safe_execute_die_) return NULL;
	  // continue;
	  continue;
	}
	INTERPRET_THROW(x);
      }
      if (syscall_return.IsNot()) {
	cout << "Syscall IsNot syscall_value:" << syscall_value << endl;
	cout << "num_params:" << num_params << endl;
	for (int64 i=0; i<num_params; i++) 
	  cout << stack_top_[-1 - i] << endl;
	INTERPRET_THROW(UNKNOWN_EXCEPTION);
	// CHECK(false);
      }
      
      *stack_top_ = syscall_return;
      stack_top_++;
      ip_++;
      continue;
    }

  HLESS_OP_label: {
      Thing res = stack_top_[-2] < stack_top_[-1] ? T : NIL;
      stack_top_ -= 1;
      stack_top_[-1] = res;      
      ip_++;
      continue;
    }
    INTERPRET_THROW(UNKNOWN_EXCEPTION);
     
  HASH_OP_label: {
      ip_++;
      uint64 num_params = (*ip_++).GetInteger();
      stack_top_ -= (num_params - 1);
      stack_top_[-1] = HashToThing(stack_top_ - num_params, num_params);
      continue;
    }

  WEAK_REF_OP_label: {
      ip_++;
      Thing arg = stack_top_[-1];
      if (arg == MISSING) INTERPRET_THROW(TYPE_EXCEPTION);
      if (arg.IsMutable()) INTERPRET_THROW(TYPE_EXCEPTION);
      if (arg.IsArray()) {
	stack_top_[-1] = (arg.ID() & ~0x7ull) | INTEGER;
      } else {
	stack_top_[-1] = a_->MakeImmutableArray2(LOCAL_ALLOCATION, QUOTE, arg);
      }
      continue;
    }

    // we should also have a THING_PAIR_OP
  WEAK_DEREF_OP_label: {
    ip_++;
    Thing arg = stack_top_[-1];
    if (arg.IsInteger()) {
      Thing ret = (arg.data_ & ~0x7ull) | INDIRECT_ARRAY;
      if (!ret.MaybeGetBox()) stack_top_[-1] = MISSING;
      else stack_top_[-1] = ret;
      continue;
    }
    if ((!arg.IsArray()) ||
	(arg.ArraySize() != 2) ||
	(arg.Ref(0) != QUOTE)) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_[-1] = arg.Ref(1);
    continue;
    }

  MLN_OP_label: 
    {
      ip_++;
      if (!stack_top_[-1].IsInteger()) INTERPRET_THROW(TYPE_EXCEPTION);
      int64 i_param = stack_top_[-1].GetInteger();
      stack_top_[-1] = NIL;
      if (i_param > 0)
	stack_top_[-1] = Thing::MakeInteger(MLn(i_param));
      continue;
    }

  LN_OP_label:
    ip_++;
    if (!stack_top_[-1].IsNumber()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_[-1] = Thing::MakeDouble(log(stack_top_[-1].GetDouble()));
    continue;

  EXP_OP_label:
    ip_++;
    if (!stack_top_[-1].IsNumber()) INTERPRET_THROW(TYPE_EXCEPTION);
    stack_top_[-1] = Thing::MakeDouble(exp(stack_top_[-1].GetDouble()));
    continue;    

  SORT_OP_label: {
      ip_++;
      Thing width_t = stack_top_[-2];
      if (!width_t.IsInteger()) INTERPRET_THROW(TYPE_EXCEPTION);
      int64 width = width_t.GetInteger();
      if (width <= 0) INTERPRET_THROW(UNKNOWN_EXCEPTION);
      Thing array = stack_top_[-1];
      if (!array.IsArray()) INTERPRET_THROW(TYPE_EXCEPTION);
      if (!array.IsMutable()) INTERPRET_THROW(TYPE_EXCEPTION);
      // TODO: maybe break if it will take too long. 
      if (array.ArraySize() % width) INTERPRET_THROW(UNKNOWN_EXCEPTION);
      SortMArray(width, array);
      stack_top_[-2] = stack_top_[-1];
      stack_top_--;
      continue;
    }

  CLEAN_FRAME_OP_label: {
      ip_++;
      int64 f_times = ip_->GetInteger();
      stack_top_[-1 - f_times] = stack_top_[-1];
      stack_top_ -= f_times;
      ip_++;
      continue;
    }

  ARRAY_OP_label: {
    ip_++;
    int64 size = (*ip_++).GetInteger();
    bool array_ok = true;
    for (int32 cc=0; cc<size; cc++) {
      Thing o = stack_top_[cc-size];
      if (o.IsMutable()) {
	array_ok = false;
	break;
      }
    }
    if (!array_ok) { INTERPRET_THROW(TYPE_EXCEPTION); }
    Thing new_array = 
      a_->MakeImmutableArray(LOCAL_ALLOCATION, stack_top_-size, size);
    if (new_array.IsNot()) INTERPRET_THROW(UNKNOWN_EXCEPTION);
    stack_top_ -= size;
    *stack_top_ = new_array;
    stack_top_++;
    continue;
    }

  MARRAY_OP_label: {
      ip_++;
      int64 length = (*ip_).GetInteger();
      Thing ret = a_->MakeMutableArray();
      Box *retbox = ret.GetBox();
      a_->ResizeMutableArray(retbox, length);
      for (int64 i=0; i<length; i++)
	ret.Ref(i) = stack_top_[i - length];
      stack_top_ -= length;
      *stack_top_ = ret;
      stack_top_++;
      ip_++;
      continue;
    }

  GETTYPE_OP_label: {
    ip_++;
    stack_top_[-1] = Thing::MakeInteger(stack_top_[-1].GetType());
    continue;
    }
    
  ARRAYP_OP_label: {
    ip_++;
    stack_top_[-1] = (stack_top_[-1].IsArray()) ? T : NIL;
    continue;
    }

  MUTABLEP_OP_label: {
    ip_++;
    stack_top_[-1] = (stack_top_[-1].IsMutable()) ? T : NIL;
    continue;
    }

  TOKENP_OP_label: {
      ip_++;
      stack_top_[-1] = (stack_top_[-1].IsToken()) ? T : NIL;
      continue;
    }

  CHARP_OP_label: {
    ip_++;
    stack_top_[-1] = (stack_top_[-1].IsChar()) ? T : NIL;
    continue;
    }

  INTEGERP_OP_label: {
    ip_++;
    stack_top_[-1] = (stack_top_[-1].IsInteger()) ? T : NIL;
    continue;
    }
    
  SYMBOLP_OP_label: {
    ip_++;
    stack_top_[-1] = (stack_top_[-1].GetType() == SYMBOL) ? T : NIL;
    continue;
    }

  NATIVEP_OP_label: {
    ip_++;
    stack_top_[-1] = (stack_top_[-1].GetType() == NATIVE_FUNCTION) ? T : NIL;
    continue;
    }

  SPECIALP_OP_label: {
    ip_++;
    stack_top_[-1] = (stack_top_[-1].GetType() == SPECIAL) ? T : NIL;
    continue;
    }

  GLOBALP_OP_label: {
      ip_++;
      Thing symbol = stack_top_[-1];
      stack_top_[-1] = G_INTERP->globals_ % symbol ? T : NIL;
      continue; 
    }
    
  AREF_OP_label: {
      Thing array = stack_top_[-2];
      if (!array.IsArray()) INTERPRET_THROW(TYPE_EXCEPTION);
      Box * arrayb = array.GetBox();
      Thing index = stack_top_[-1]; 
      if (!index.IsInteger()) INTERPRET_THROW(TYPE_EXCEPTION);
      ip_++;
      int64 index_n = index.GetInteger();
      if ((index_n < 0) 
	  || (index_n >= (int64)arrayb->ArraySize())) INTERPRET_THROW(UNKNOWN_EXCEPTION);
      stack_top_ -= 2;
      *stack_top_ = arrayb->Ref(index_n);
      stack_top_++;
      continue;
    }

  CONST_AREF_OP_label: {
    ip_++;
    int64 index = ip_->GetInteger();
    Thing array = stack_top_[-1];
    if (!array.IsArray()) {
      // cout << "Trying to perform const_aref_op on " << array << endl;
      INTERPRET_THROW(TYPE_EXCEPTION);
    }
    Box * arrayb = array.GetBox();
    if ((index < 0) || (index >= (int64)arrayb->ArraySize())) 
      INTERPRET_THROW(UNKNOWN_EXCEPTION);
    ip_++;
    stack_top_[-1] = arrayb->Ref(index);
    continue;
    }
    
  MSET_OP_label: {
      Thing array = stack_top_[-3];
      if (!array.IsArray()) INTERPRET_THROW(TYPE_EXCEPTION);
      Box * arrayb = array.GetBox();
      if (!arrayb->IsMutable()) INTERPRET_THROW(TYPE_EXCEPTION);
      Thing index = stack_top_[-2];
      if (!index.IsInteger()) INTERPRET_THROW(TYPE_EXCEPTION);
      int64 index_n = index.GetInteger();
      if ((index_n < 0) || (index_n >= (int64)arrayb->ArraySize())) 
	INTERPRET_THROW(UNKNOWN_EXCEPTION);
      Thing value = stack_top_[-1];
      arrayb->Ref(index_n) = value;
      stack_top_[-3] = stack_top_[-1];
      stack_top_ -= 2;
      ip_++;
      continue;
    }

  SET_OP_label: {
      ip_++;
      int64 constant_pos = ip_->GetInteger();
      // cout << "old value = " << stack_top_[constant_pos] << endl;
      stack_top_[constant_pos] = stack_top_[-1];
      // cout << "new value = " << stack_top_[constant_pos] << endl;
      ip_++;
      continue;
    }

  LENGTH_OP_label: {
    ip_++;
    Thing array = stack_top_[-1]; 
    if (array.IsArray()) {
      stack_top_[-1] = Thing::MakeInteger(array.GetBox()->ArraySize());
      continue;
    } 
    INTERPRET_THROW(TYPE_EXCEPTION);
  }

  NODECOUNT_OP_label: {
      ip_++;
      Thing arg = stack_top_[-1]; 
      stack_top_[-1] = Thing::MakeInteger(arg.NodeCount());
      continue;
    }

  RANDOM_OP_label: {
      NoProgramCache();
      NoFunctionCache();
      Thing range = stack_top_[-1]; 
      if (!range.IsInteger()) INTERPRET_THROW(TYPE_EXCEPTION);
      int64 r = range.GetInteger();
      if (r<=0) INTERPRET_THROW(UNKNOWN_EXCEPTION);
      stack_top_[-1] = Thing::MakeInteger(rng_.Random() % r);
      ip_++;
      continue;
    }

  RETURN_OP_label: {
      // cout << "stack_top_ " << stack_top_ << endl;
      // cout << "value = " << stack_top_[-1] << endl;
    CodeStackFrame & frame = *(--code_stack_top_);
    if ((frame.cache_key_) &&
	(frame.start_function_uncachable_count_ 
	 == function_uncachable_count_) &&
	(!stack_top_[-1].IsMutable())) {
      if (frame.cached_value_.Is()) {
	if (stack_top_[-1] != frame.cached_value_) {
	  cout << "Cache error - cached = " << frame.cached_value_
	       << " computed = " << stack_top_[-1] << endl;
	  CHECK(false);
	}
      }
      a_->cache_.Store(frame.cache_key_, stack_top_[-1].data_);
    }
    Thing * new_stack_top = frame.function_in_stack_ + 1;
    new_stack_top[-1] = stack_top_[-1];
    stack_top_ = new_stack_top;
    JumpTo(frame.return_ip_);
    continue;
    }

  EXIT_OP_label: {
    return stack_top_[-1];
    }

  DEF_OP_label: {
      ip_++;
      Thing value = stack_top_[-1];
      Thing symbol = (Thing )*(ip_++);
      if (!SetGlobal(symbol, value))
	cerr << "attempt to redefine global " << symbol << endl;
      continue;
    }
    
  READ_GLOBAL_OP_label: {
      NoFunctionCache();
      ip_++;
      Thing key = (Thing )*(ip_++);
      Thing ret = GetGlobal(key);
      if (ret.Is()) {
	stack_top_[0] = ret;
	stack_top_++;
      } else {
	cout << "Global Not Found: " << key << endl;
	CodeStackFrame * frame = code_stack_top_ - 1;
	cout << "Function: " << *(frame->function_in_stack_) << endl;
	INTERPRET_THROW(GLOBAL_NOT_FOUND_EXCEPTION);
      }
      continue;
    }

  ACCESSCOUNT_OP_label: { 
      NoProgramCache();
      NoFunctionCache();    
      ip_++;
      Thing array = stack_top_[-1];
      if (array.IsArray()) {
	stack_top_[-1] = Thing::MakeInteger(array.GetBox()->LgAccessCountRef());
	continue;
      }
      INTERPRET_THROW(TYPE_EXCEPTION);
    }
    
    // Use this to store data in the instruction stream
  NOOP_OP_label: {
      ip_ += 2;
      cout << "noop" << endl;
      continue;
    }
  GLOBALIZE_OP_label: {
      ip_++;
      Thing arg = stack_top_[-1]; 
      stack_top_[-1] = a_->Globalize(arg);
      continue;
    }
  HASH_SET_OP_label: {
      ip_++;
      Thing h = stack_top_[-3];
      Thing k = stack_top_[-2];
      Thing v = stack_top_[-1];
      if (!IsMutableHash(h)) INTERPRET_THROW(TYPE_EXCEPTION);
      stack_top_ -= 2;
      HashSet(h, k, v, a_);
      stack_top_[-1] = v;
      continue;
    }
  HASH_DELETE_OP_label: {
      ip_++;
      Thing h = stack_top_[-2];
      Thing k = stack_top_[-1];
      if (!IsMutableHash(h)) INTERPRET_THROW(TYPE_EXCEPTION);
      stack_top_ -= 1;
      HashDelete(h, k, a_);
      stack_top_[-1] = NIL;
      continue;
    }
  HASH_LOOK_OP_label: {
      ip_++;
      Thing h = stack_top_[-3];
      Thing k = stack_top_[-2];
      Thing default_val = stack_top_[-1];
      if (!IsHash(h)) INTERPRET_THROW(TYPE_EXCEPTION);
      stack_top_ -= 2;
      stack_top_[-1] = HashLookDefault(h, k, default_val, a_);
      continue;
    }
  GETMODE_OP_label: {
      NoFunctionCache();
      stack_top_++;
      switch (mode_) {
      case kGenerativeMode:
	stack_top_[-1] = GENERATIVE_MODE;
	break;
      case kEconomyMode:
	stack_top_[-1] = ECONOMY_MODE;
	break;
      default:
	stack_top_[-1] = NIL;
	break;
      }
      ip_++;
      continue;
    }
  }
}

int64 Vinterpreter::TimeRemaining() {
  return handler_stack_top_[-1].clock_limit_ - clock_.Get(); 
}

// Only called on real function calls
void Vinterpreter::ProcessFuncallOp(OpCodes op) {
  // Quick stop checks
  if (SometimesOvertime()) { FailTimeLimit(); return; }
  if (code_stack_top_ == code_stack_limit_) 
    INTERPRET_THROW_RETURN(STACK_EXCEPTION);

  // Get the number of parameters passed and the code
  ip_++;
  int64 num_params_passed = 0;
  if (op == FUNCALL_OP) {
    // num_params_passed does not include the function code
    num_params_passed = ip_->GetInteger();
    ip_++;
  } else {    
    // op == APPLY_OP
    Thing params_array = stack_top_[-1];
    stack_top_--;
    if (!params_array.IsArray()) INTERPRET_THROW_RETURN(TYPE_EXCEPTION);
    Box * params_box = params_array.GetBox();
    num_params_passed = params_box->ArraySize();
    if (num_params_passed + stack_top_ >= stack_limit_) 
      INTERPRET_THROW_RETURN(UNKNOWN_EXCEPTION);
    for (int64 i=0; i<num_params_passed; i++) {
      *stack_top_ = params_box->Ref(i);
      stack_top_++;
    }
  }
  Thing code = stack_top_[-1 - num_params_passed]; CHECK(code.Is());

  if ((code.GetType() == NATIVE_FUNCTION) || 
      (code.GetType() == SPECIAL)) {
    code = GetGlobal(code);
    if (code.IsNot())
      INTERPRET_THROW_RETURN(TYPE_EXCEPTION);
  }

  Thing new_code = CompileFunctionFast(code);
  if (new_code.IsNot()) {
    optimization_depth_ = 0;
    new_code = CompileFunction(code, false);
    if (new_code.IsNot()) return; // exception has been thrown
  }
  // Compiled code is always in temporary array space
  Box * new_codeb = (Box *) new_code.data_;

  bool used_rest = false;
  // Deal with REST
  Thing params = code.Ref(1);
  int64 params_size = params.ArraySize();
  if (params_size > 0) {
    int64 num_fixed_params = params_size - 1;
    Thing last_param = params.Ref(num_fixed_params);
    if (last_param == REST || last_param == MREST) {
      int64 num_rest_params = num_params_passed - num_fixed_params;
      if (num_rest_params >= 0) {
	stack_top_ -= num_rest_params;
	*stack_top_ = 
	  (last_param == MREST) ? 
	  a_->MakeMutableArray(stack_top_, num_rest_params) :
	  a_->MakeImmutableArray(LOCAL_ALLOCATION, stack_top_, 
				 num_rest_params);
	stack_top_++;
	num_params_passed = params_size;
	used_rest = true;
      }
    }
  }

  // Is the number of parameters passed correct
  Thing * new_code_ref_0 = &(new_codeb->Ref(0));
  if (new_codeb->ArraySize() + stack_top_ >= stack_limit_) 
    INTERPRET_THROW_RETURN(STACK_EXCEPTION);
  int64 num_params_needed = (new_code_ref_0 + ARITY)->GetInteger();
  if (num_params_needed != num_params_passed) {
    // do we really need ((lambda (x) x)) -> (lambda (x) x)
    // if (num_params_passed == 0) return;
    INTERPRET_THROW_RETURN(ARITY_EXCEPTION);
  }
  
  // we're running the function.  
  CodeStackFrame & frame = *code_stack_top_;
  frame.return_ip_ = ip_;
  frame.function_in_stack_ = stack_top_ - 1 - num_params_passed;
  frame.start_function_uncachable_count_ 
    = function_uncachable_count_;
  frame.compiled_code_ = new_code;
  frame.cache_key_ = 0;

  // Determine whether to look something up in the cache
  bool cache_now = true;
  Thing * local_stack_begin = stack_top_ - num_params_needed - 1;
  if (cache_now)
    for (Thing * checker = local_stack_begin; checker < stack_top_; checker++)
      if ((*checker).IsMutable()) {
	cache_now = false;
	break;
      }
  if (cache_now) {
    frame.cache_key_ = HashStack(local_stack_begin, stack_top_);
    Thing cached_val;
    frame.cached_value_ = NULL;
    if (a_->cache_.Lookup(frame.cache_key_, &cached_val.data_)) {
      // FUNCTION CACHING
      frame.cached_value_ = cached_val;
      CHECK(a_->LocalMemoryOK(cached_val));
      stack_top_ -= num_params_needed;
      stack_top_[-1] = cached_val;
      return; 
    }
  }
  
  // actually execute
  code_stack_top_++;
  JumpTo(new_code_ref_0 + CODE_INFO_MAX);
  return;
}

// Recognize constant values
Thing Vinterpreter::
ConstantValue(Thing code) {
  if (code.IsSymbol()) { return NULL; }
  if ( !code.IsArray()) return code;
  Box * codeb = code.GetBox();
  if ( (codeb->ArraySize() == 2) &&
       (codeb->Ref(0) == QUOTE)) return codeb->Ref(1);
  if ( (codeb->ArraySize() == 3) && 
       ( (codeb->Ref(0) == LAMBDA) || (codeb->Ref(0) == CLOSURE) )) return code;
  return NULL;
}

// Called from the top level
Thing Vinterpreter::CompileWithExit(Thing & code) {
  compile_.clear();
  compile_log_.clear();
  locals_.clear();
  bool success = Compile(code, 0);
  if (!success) {
    // cout << "Compile failure at top level " << ToString(code) << endl;
    return NULL;
  }
  compile_.push_back(Thing::MakeInteger(EXIT_OP));
  Thing ret = a_->MakeImmutableArray(LOCAL_ALLOCATION, compile_);
  CHECK(ret.Is());
  compile_.clear();
  return ret;
}

#define RECURSIVE_COMPILE_FAIL return NULL
#define COMPILE_THROW(x) \
  { Throw(x, "COMPILE " + itoa(__LINE__) + " " + ToString(code)); \
    return NULL; }
#define COMPILE_TIMEOUT { FailTimeLimit(); return NULL; }

#define PUSH_INTEGER(x) compile_.push_back(Thing::MakeInteger(x))

Thing Vinterpreter::CompileFunction(Thing & code, bool inlining) {
  if (!inlining) { locals_.clear(); compile_.clear(); compile_log_.clear(); }

  // Remember this to undo inlining locals
  int32 old_locals_size = locals_.size();

  // Check that the code is code
  if (!code.IsArray()) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
  Box * codeb = code.GetBox();
  if (codeb->ArraySize() != 3 
      || codeb->Ref(0) != LAMBDA || !codeb->Ref(1).IsArray())
    COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
  
  Thing params = codeb->Ref(1);
  Box * paramsb = params.GetBox();
  Thing child_code = codeb->Ref(2);
  int arity = paramsb->ArraySize();
  
  // Push back new locals
  locals_.push_back(make_pair(SELF, -1 - arity));
  for (int i=0; i<arity; i++) {
    Thing v = paramsb->Ref(i);
    if (!v.IsSymbol()) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    // for debugging and inlining we need to push locals onto the debug stack
    if (inlining) {
      PUSH_INTEGER(DEBUG_VAR_INTRO_OP); 
      compile_.push_back(v);
      PUSH_INTEGER(-arity + i + 1);
    }
    locals_.push_back(make_pair(v, i - arity));
  }

  // Arity and compile_log
  if (!inlining) {
    PUSH_INTEGER(NOOP_OP); PUSH_INTEGER(arity);
    // for the compile log, not needed in inlining
    PUSH_INTEGER(NOOP_OP); PUSH_INTEGER(0); 
  }

  bool success = Compile(child_code, 0);
  if (!success) RECURSIVE_COMPILE_FAIL;

  // return of T indicates inlining compilation was successful
  if (inlining) {
    locals_.resize(old_locals_size);
    PUSH_INTEGER(DEBUG_VAR_REMOVE_OP); PUSH_INTEGER(arity);
    return T; }

  // All of this is for regular function compiles
  compile_.push_back(Thing::MakeInteger(RETURN_OP));
  Thing compile_log = a_->MakeImmutableArray(LOCAL_ALLOCATION, compile_log_);
  CHECK(compile_log.Is());
  compile_[COMPILE_LOG] = compile_log;
  Thing ret =  a_->MakeImmutableArray(LOCAL_ALLOCATION, compile_);
  CHECK(ret.Is());
  uint64 thing_cache_key = Fingerprint(code.ID(), 0x29038484093ll);
  a_->cache_.Store(thing_cache_key, ret.data_);
  return ret;
}

// locals maps local variables to positions relative to the frame pointer
bool Vinterpreter::Compile(Thing code, 
			   int stack_above_frame) {
  //cout << "Compiling " << ToString(code) << endl;
  // Make sure we have time to run the compile
  if (Overtime()) COMPILE_TIMEOUT;

  CompileFrame cf(this);
  if (compile_depth_ > 100) COMPILE_TIMEOUT;

  CompileLogger logger(this, code);
  
  // Anything recognized as a constant gets a PUSH_THING_OP
  {
    Thing cv = ConstantValue(code);
    if (cv.Is()) {
      PUSH_INTEGER(PUSH_THING_OP);
      compile_.push_back(cv);
      return true;
    }
  }

  if (code.IsSymbol()) { 
    int32  pos = -1000000;
    int32 locals_size = locals_.size();
    for (int32 i=0; i<locals_size; i++) {
      int32 index = (locals_size - 1) - i;
      if (locals_[index].first == code) {
	pos = locals_[index].second;
	break;
      }
    }
    if (pos != -1000000) {
      // local variable
      PUSH_INTEGER(S_OP); 
      PUSH_INTEGER(pos - stack_above_frame);
      return true;
    } 
    // it's a global
    Thing compile_time_value = GetGlobal(code);
    if (compile_time_value.Is()) {
      PUSH_INTEGER(PUSH_THING_OP);
      compile_.push_back(compile_time_value);
    } else {
      PUSH_INTEGER(READ_GLOBAL_OP);
      compile_.push_back(code);
    }
    return true;
  }
  
  // By now we should only be compiling arrays. Anything else would
  // have been a constant or a symbol in the local scope
  CHECK(code.IsArray());
  Box * codeb = code.GetBox();

  // Empty arrays probably shouldn't be compiled
  if (codeb->ArraySize() == 0) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
  
  // Handle based on the car of the code
  Thing car = codeb->Ref(0);

  // Quotes should be handled by the constant handling part of the code
  if (car == QUOTE) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);

  // BACKQUOTES may allocate memory and result in a recursive call to Compile
  if (car == BACKQUOTE) {
    if (codeb->ArraySize() != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    int64 nc = codeb->Ref(1).NodeCount();
    if ((nc == 0) || (nc > 10000)) { // avoid blowing c stack
      COMPILE_TIMEOUT;
    }
    if (Overtime()) COMPILE_TIMEOUT;
    Thing bqe = codeb->Ref(1);
    Thing backquote_expansion = ExpandBackquote(a_, bqe);
    return Compile(backquote_expansion, stack_above_frame);
  }
  
  // Handle FORGET 
  if (car == FORGET) {
    if (codeb->ArraySize() != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    PUSH_INTEGER(TIME_OP);
    Thing child_code = codeb->Ref(1);
    if (!Compile(child_code, stack_above_frame + 1)) 
      RECURSIVE_COMPILE_FAIL;
    PUSH_INTEGER(FORGET_OP);
    return true;
  }

  // Handle LET 
  if (car == LET) {
    if (codeb->ArraySize() != 4) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    Thing var = codeb->Ref(1);
    Thing val_code = codeb->Ref(2);
    Thing child_code = codeb->Ref(3);
    if (!var.IsSymbol()) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    if (!Compile(val_code, stack_above_frame)) 
      RECURSIVE_COMPILE_FAIL;
    PUSH_INTEGER(DEBUG_VAR_INTRO_OP); 
    compile_.push_back(var);
    PUSH_INTEGER(0);
    locals_.push_back(make_pair(var, stack_above_frame));
    stack_above_frame++;
    if (!Compile(child_code, stack_above_frame)) 
      RECURSIVE_COMPILE_FAIL;
    locals_.pop_back();
    PUSH_INTEGER(DEBUG_VAR_REMOVE_OP); PUSH_INTEGER(1);
    PUSH_INTEGER(CLEAN_FRAME_OP); PUSH_INTEGER(1);
    return true;
  }

  // Handle IF
  if (car == IF) {
    int code_size = codeb->ArraySize();
    if (code_size != 3 && code_size !=4 ) 
      COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    Thing test_code = codeb->Ref(1);
    Thing true_code = codeb->Ref(2);
    Thing false_code = (code_size == 3 ? NIL : codeb->Ref(3));
    if (!Compile(test_code, stack_above_frame)) 
      RECURSIVE_COMPILE_FAIL;
    PUSH_INTEGER(TEST_JUMP_OP);
    PUSH_INTEGER(-1);
    int64 first_jump = compile_.size() - 1;
    if (!Compile(true_code, stack_above_frame)) 
      RECURSIVE_COMPILE_FAIL;
    PUSH_INTEGER(JUMP_OP);
    PUSH_INTEGER(-1);
    int64 second_jump = compile_.size()-1;
    compile_[first_jump] = Thing::MakeInteger(compile_.size() - first_jump);
    if (!Compile(false_code, stack_above_frame)) 
      RECURSIVE_COMPILE_FAIL;
    compile_[second_jump] = Thing::MakeInteger(compile_.size() - second_jump);
    // Jumping into nothingness
    return true;
  }

  // Handle AND and OR
  if ( (car == AND) || (car == OR) ) {
    bool is_or = (car == OR);
    if (codeb->ArraySize() < 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    PUSH_INTEGER(PUSH_THING_OP);
    compile_.push_back(is_or?NIL:T);
    uint64 start_looking_for_jumps = compile_.size();
    for (uint64 i=1; i<codeb->ArraySize(); i++) {
      PUSH_INTEGER(POP_OP);
      Thing child_code = codeb->Ref(i);
      if (!Compile(child_code, stack_above_frame)) 
	RECURSIVE_COMPILE_FAIL;
      PUSH_INTEGER(is_or ? OR_OP : AND_OP);
      compile_.push_back(NULL); // will be replaced by jump location
    }
    // jump target
    for (uint32 i=start_looking_for_jumps; i<compile_.size(); i++) {
      if (compile_[i].IsNot())
	compile_[i] = Thing::MakeInteger( compile_.size() - i);
    }
    return true;
  }

  // Handle LIMIT, CATCH, DEBUG
  if ( (car == LIMIT) || (car == CATCH) || (car == DEBUG) ){
    if (codeb->ArraySize() != 3) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    Thing limit_code = codeb->Ref(1);
    Thing run_code = codeb->Ref(2);
    if (!Compile(limit_code, stack_above_frame)) 
      RECURSIVE_COMPILE_FAIL;
    PUSH_INTEGER(PUSH_HANDLER_OP);
    compile_.push_back(car);
    int64 handler_jump = compile_.size();
    PUSH_INTEGER(-1);
    if (!Compile(run_code, stack_above_frame)) 
      RECURSIVE_COMPILE_FAIL;
    PUSH_INTEGER(POP_HANDLER_OP);
    compile_[handler_jump] = Thing::MakeInteger(compile_.size() - handler_jump);
    return true;
  }

  // handle def special form
  if (car == DEF) {
    if (codeb->ArraySize() != 3) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    Thing symbol = codeb->Ref(1);
    Thing value_code = codeb->Ref(2);
    // if (!symbol.IsSymbol()) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    if (!Compile(value_code, stack_above_frame)) 
      RECURSIVE_COMPILE_FAIL;
    PUSH_INTEGER(DEF_OP);
    compile_.push_back(symbol);
    return true;
  }

  if (car == DOTIMES || car == REPEAT) {
    // we will place three items on the stack - from bottom to top 
    //  0: n (the total number of iterations)
    //  1: array to be constructed
    //  2: current index
    if (codeb->ArraySize() != 4) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    Thing var = codeb->Ref(1);
    Thing n_code = codeb->Ref(2);
    Thing child_code = codeb->Ref(3);
    if (!var.IsSymbol()) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    if (!Compile(n_code, stack_above_frame)) RECURSIVE_COMPILE_FAIL;
    PUSH_INTEGER(START_DOTIMES_OP); // set up array and current index
    compile_.push_back(car);
    int64 forward_jump = compile_.size();
    PUSH_INTEGER(-1);
    locals_.push_back(make_pair(var, stack_above_frame + 2));
    int64 backward_jump_target = compile_.size();
    if (!Compile(child_code, stack_above_frame + 3)) 
      RECURSIVE_COMPILE_FAIL;
    locals_.pop_back();
    compile_[forward_jump] = Thing::MakeInteger(compile_.size() - forward_jump);
    PUSH_INTEGER(NEXT_DOTIMES_OP);
    PUSH_INTEGER(backward_jump_target - compile_.size());
    return true;
  }
  
  // Capture constant + and - calls
  if ((car == PLUS) || (car == MINUS)) {
    if (codeb->ArraySize() != 3)  COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    Thing r2 = codeb->Ref(2);
    if (r2.IsInteger()) {
      int64 addend = r2.GetInteger() * ((car == PLUS) ? 1 : -1);
      Thing r1 = codeb->Ref(1);
      if (!Compile(r1, stack_above_frame)) 
	RECURSIVE_COMPILE_FAIL;
      PUSH_INTEGER(CONST_PLUS_OP);
      PUSH_INTEGER(addend);
      return true;
    }
  }
  
  if (car == AREF) {
    if (codeb->ArraySize() != 3) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    Thing r2 = codeb->Ref(2);
    if (r2.IsInteger()) {
      int64 index = r2.GetInteger();
      Thing r1 = codeb->Ref(1);
      if (!Compile(r1, stack_above_frame)) 
	RECURSIVE_COMPILE_FAIL;
      PUSH_INTEGER(CONST_AREF_OP);
      PUSH_INTEGER(index);
      return true;
    }
  } 
  
  // constant = calls
  if (car == EQUAL) {
    if (codeb->ArraySize() != 3) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    Thing r2 = codeb->Ref(2);
    Thing c_r2 = ConstantValue(r2);
    if (c_r2.Is()) {
      Thing r1 = codeb->Ref(1);
      if (!Compile(r1, stack_above_frame)) 
	RECURSIVE_COMPILE_FAIL;
      PUSH_INTEGER(CONST_EQUAL_OP);
      compile_.push_back(c_r2);
      return true;
    }
  }

  // Capture constant * calls.
  if (car == TIMES) {
    if (codeb->ArraySize() != 3) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    Thing r2 = codeb->Ref(2);
    if (r2.IsInteger()) {
      int64 multiplicand  = r2.GetInteger();
      Thing r1 = codeb->Ref(1);
      if (!Compile(codeb->Ref(1), stack_above_frame)) 
	RECURSIVE_COMPILE_FAIL;
      PUSH_INTEGER(CONST_TIMES_OP);
      compile_.push_back(Thing::MakeInteger(multiplicand));
      return true;
    }
  }

  if (car == SET) {
    Thing variable = codeb->Ref(1);
    if (!(variable.IsSymbol())) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    if (!Compile(codeb->Ref(2), stack_above_frame))
      RECURSIVE_COMPILE_FAIL;
    PUSH_INTEGER(SET_OP);
    int32 pos = LocalSymbolPosition(variable);
    if (pos == -1000000) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
    PUSH_INTEGER(pos - stack_above_frame - 1);
    return true;
  }

  // Handle all explicit native functions
  if (car.GetType() == NATIVE_FUNCTION) {
    // First push all parameters in order 
    int num_params = codeb->ArraySize() - 1;
    for (int i=0; i<num_params; i++) {
      Thing arg = codeb->Ref(i+1);
      if (!Compile(arg, stack_above_frame + i))
	RECURSIVE_COMPILE_FAIL;
    }
    switch(car.GetUnboxedValue()) {
      // PLUS and MINUS test for arity above in the constant abbreviations
    case NATIVE_TO_INT:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(TO_INT_OP);
      break;
    case NATIVE_TO_DOUBLE:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(TO_DOUBLE_OP);
      break;
    case NATIVE_INT_CHAR:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(INT_CHAR_OP);
      break;
    case NATIVE_PLUS:
      PUSH_INTEGER(PLUS_OP);
      break;
    case NATIVE_MINUS:
      PUSH_INTEGER(MINUS_OP);
      break;
    case NATIVE_TIMES:
      PUSH_INTEGER(TIMES_OP);
      break;
    case NATIVE_MOD:
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(MOD_OP);
      break;
    case NATIVE_DIVIDE:
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(DIVIDE_OP);
      break;
    case NATIVE_EQUAL:
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(EQUAL_OP);
      break;
    case NATIVE_LESS:
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(LESS_THAN_OP);
      break;
    case NATIVE_NOT:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(NOT_OP);
      break;
    case NATIVE_TOSTRING:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(TOSTRING_OP);
      break;
    case NATIVE_TOSYMBOL:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(TOSYMBOL_OP);
      break;
    case NATIVE_FUNCALL:
      PUSH_INTEGER(FUNCALL_OP);
      if (num_params == 0) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(num_params - 1);
      break;
    case NATIVE_APPLY:
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(APPLY_OP);
      break;
    case NATIVE_HLESS:
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(HLESS_OP);
      break;
    case NATIVE_HASH:
      PUSH_INTEGER(HASH_OP);
      PUSH_INTEGER(num_params);
      break;
    case NATIVE_WEAK_REF:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(WEAK_REF_OP);
      break;
    case NATIVE_WEAK_DEREF:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(WEAK_DEREF_OP);
      break;
    case NATIVE_MLN:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(MLN_OP);
      break;
    case NATIVE_LN:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(LN_OP);
      break;
    case NATIVE_EXP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(EXP_OP);
      break;
    case NATIVE_SORT: 
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(SORT_OP);
      break;
    case NATIVE_ARRAY:
      PUSH_INTEGER(ARRAY_OP);
      PUSH_INTEGER(num_params);
      break;
    case NATIVE_MARRAY:
      PUSH_INTEGER(MARRAY_OP);
      PUSH_INTEGER(num_params);
      break;
    case NATIVE_GETTYPE:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(GETTYPE_OP);
      break;
    case NATIVE_ARRAYP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(ARRAYP_OP);
      break;
    case NATIVE_MUTABLEP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(MUTABLEP_OP);
      break;
    case NATIVE_TOKENP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(TOKENP_OP);
      break;
    case NATIVE_CHARP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(CHARP_OP);
      break;
    case NATIVE_INTEGERP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(INTEGERP_OP);
      break;
    case NATIVE_SYMBOLP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(SYMBOLP_OP);
      break;  
    case NATIVE_NATIVEP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(NATIVEP_OP);
      break;  
    case NATIVE_SPECIALP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(SPECIALP_OP);
      break;  
    case NATIVE_GLOBALP:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(GLOBALP_OP);
      break;  
    case NATIVE_AREF:
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(AREF_OP);
      break;
    case NATIVE_MSET:
      if (num_params != 3) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(MSET_OP);
      break;
    case NATIVE_CAR:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(CONST_AREF_OP);
      PUSH_INTEGER(0);
      break;
    case NATIVE_CDR:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(CONST_AREF_OP);
      PUSH_INTEGER(1);
      break;
    case NATIVE_CONS:
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(ARRAY_OP);
      PUSH_INTEGER(2);
      break;
    case NATIVE_PROGN:
      if (num_params == 0) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(CLEAN_FRAME_OP);
      PUSH_INTEGER(num_params - 1);
      break;
    case NATIVE_LENGTH:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(LENGTH_OP);
      break;
    case NATIVE_ACCESSCOUNT:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(ACCESSCOUNT_OP);
      break;
    case NATIVE_NODECOUNT:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(NODECOUNT_OP);
      break;      
    case NATIVE_RANDOM:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(RANDOM_OP);
      break;
    case NATIVE_PRINT:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(PRINT_OP);
      break;
    case NATIVE_PRINTSTRING:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(PRINT_STRING_OP);
      break;
    case NATIVE_GETLIMIT:
      if (num_params != 0) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(GETLIMIT_OP);
      break;
    case NATIVE_CRASH:
      if (num_params != 0) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(CRASH_OP);
      break;
    case NATIVE_THROW:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(THROW_OP);
      break;
    case NATIVE_RESIZE: 
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(RESIZE_OP);
      break;
    case NATIVE_RG:
      if (num_params != 0) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(RG_OP);
      break;
    case NATIVE_GLOBALIZE:
      if (num_params != 1) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(GLOBALIZE_OP);
      break;
    case NATIVE_HASH_SET:
      if (num_params != 3) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(HASH_SET_OP);
      break;
    case NATIVE_HASH_DELETE:
      if (num_params != 2) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(HASH_DELETE_OP);
      break;
    case NATIVE_HASH_LOOK:
      if (num_params != 3) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(HASH_LOOK_OP);
      break;
    case NATIVE_GETMODE:
      if (num_params != 0) COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      PUSH_INTEGER(GETMODE_OP);
      break;
    default:
      COMPILE_THROW(COMPILE_SYNTAX_EXCEPTION);
      break;
    }
    return true;
  }

  // Is the car a system call thing
  if (car.IsSyscall()) {
    int num_params = codeb->ArraySize() - 1;
    // PUSH_INTEGER(PUSH_THING_OP);
    // compile_.push_back(codeb->Ref(0));
    for (int i=0; i<num_params; i++) {
      Thing arg = codeb->Ref(1 + i);
      if (!Compile(arg, stack_above_frame + i))
	RECURSIVE_COMPILE_FAIL;
    }
    PUSH_INTEGER(SYSCALL_OP);
    PUSH_INTEGER(car.GetUnboxedValue());
    PUSH_INTEGER(num_params);
    PUSH_INTEGER(CLEAN_FRAME_OP);
    PUSH_INTEGER(num_params);
    return true;
  }

  //  Implicit funcall
  Thing * arg0 = &(codeb->Ref(0));

  int32 num_elements = codeb->ArraySize();
  for (int32 i=0; i<num_elements; i++) {
    Thing arg = *(arg0 + i);
    if (!Compile(arg, stack_above_frame + i)) 
      RECURSIVE_COMPILE_FAIL;
  }

  // inlining optimization
  bool compile_time_code_known = false;
  Thing compile_time_code = NULL;
  if (arg0->IsSymbol() && (LocalSymbolPosition(*arg0) == -1000000)) {
    compile_time_code = GetGlobal(*arg0);
    if (compile_time_code.Is())
      compile_time_code_known = true;
  }

  if (compile_time_code_known && (optimization_depth_ < kInliningDepth)) {
    // cout << "inlining " << *arg0 << endl << compile_time_code << endl;
    optimization_depth_++;
    Thing inline_check = CompileFunction(compile_time_code, true);
    optimization_depth_--;
    if (inline_check != T) return false;
    PUSH_INTEGER(CLEAN_FRAME_OP); PUSH_INTEGER(num_elements);
    return true;
  }

  PUSH_INTEGER(FUNCALL_OP);
  CHECK(num_elements > 0);
  PUSH_INTEGER(num_elements - 1);
  return true;
}

void Vinterpreter::ClearStacks() {
  stack_top_ = stack_;
  debug_stack_top_ = debug_stack_;
  code_stack_top_ = code_stack_;
}

Thing Vinterpreter::SafeExecute
(Thing code_in, int64 limit, uint64 mode, Thing exceptions) {
  if (mode == kEconomyMode) {
    CHECK(debug_stack_top_ == debug_stack_);
  }
  // cout << "::SafeExecute code:" << code_in << endl;
  StateSaver state_saver(this);
  // HandlerFrame * old_state = handler_stack_top_;
  PushHandlerFrame(clock_.Get() + limit, exceptions, SAFEEXECUTE);
  int64 old_program_uncachable_count = program_uncachable_count_;
  mode_ = mode;
  run_global_ = a_->MakeMutableArray(3, NIL);
  Thing code = EvaledCode(code_in); CHECK(code.Is());
  Thing result;
  safe_execute_die_ = false;
  Thing comp = CompileWithExit(code);
  if (comp.IsNot()) return NULL;
  Box * compb = comp.GetBox();
  result = Execute(&(compb->Ref(0)));
  if (mode == kGenerativeMode && 
      program_uncachable_count_ != old_program_uncachable_count)
    return NULL;
  return result;
}

void Vinterpreter::Debug() {
  // cout << "*** Debugging ***" << endl;
  

  // Some simple diagnostics
  if (failure_string_ != "") cout << failure_string_ << endl;

  // Start looking at the stack
  Thing * debug_stack_top = debug_stack_top_;
  const Thing * crash_ip = ip_;
  for (int i=0; i<10; i++) {
    int from_bottom = code_stack_top_ - code_stack_ - i;
    if (from_bottom <= 0) break;
    const CodeStackFrame& csf = code_stack_top_[-1-i];
    cout << endl;
    cout << "----------" << "Frame " << i << "----------" << endl;
    DebugFrame(crash_ip, csf.compiled_code_);
    cout << endl;
    DebugParameters(csf.function_in_stack_, &debug_stack_top);
    crash_ip = csf.return_ip_;
  } 
  cout << endl;
}

void Vinterpreter::DebugParameters
(Thing * function_in_stack, Thing **debug_stack_top) {
  // cout << *function_in_stack << endl;
  Thing params = function_in_stack->Ref(1);
  int num_params = params.ArraySize();
  for (int i=0; i<num_params; i++) 
    cout << params.Ref(i) << " = " << ToStringShort(function_in_stack[i+1]) << endl;
  
  Thing * local_var_position = (*debug_stack_top) - 2;
  while (local_var_position >= debug_stack_) {
    Thing local_var = *local_var_position;
    int64 offset = local_var_position[1].GetInteger();
    Thing * local_value_position = stack_ + offset;
    Thing local_value = *local_value_position;
    if (local_value_position <= function_in_stack) break;
    cout << "local " << local_var << " = " << ToStringShort(local_value) << endl;
    local_var_position -= 2;
  }
  *debug_stack_top = local_var_position + 2;
}

// You should only be here inside a function call
void Vinterpreter::DebugFrame(const Thing * ip, Thing compiled_code) {
  // cout << "Compiled code: " << ToString(compiled_code) << endl;
  Box * compiled_codeb = compiled_code.GetBox();

  Thing log = compiled_codeb->Ref(3);
  Box * logb = log.GetBox();
  int64 crash_relative_instruction = ip - &compiled_codeb->Ref(0);
  // cout << "cri: " << crash_relative_instruction << endl;

  // Find a position in the log just past where you are interested
  int64 look = 0;
  for (; true; look++) {
    if (look == (int64) logb->ArraySize() / COMPILE_LOG_INFO_SIZE)
      break;
    int64 i_pos = look * COMPILE_LOG_INFO_SIZE + COMPILE_LOG_INSTRUCTION;
    int64 relative_instruction = logb->Ref(i_pos).GetInteger();
    // cout << "ri: " << relative_instruction << endl;
    if (relative_instruction >= crash_relative_instruction)
      break;
  }

  // Scan the log backwards
  int32 depth = 0;
  int32 max_depth = 0;
  int32 depth_limit = 4;
  for (int64 scan = look-1; scan >= 0; scan--) {
    int64 pos = scan * COMPILE_LOG_INFO_SIZE;
    CompileLogAction a = 
      (CompileLogAction) logb->Ref(pos + COMPILE_LOG_ACTION).GetInteger();
    if (a == COMPILE_EXIT) depth--;
    if (a == COMPILE_ENTER) {
      depth++;
      if (depth > max_depth) {
	max_depth = depth;
	if (depth < depth_limit) {
	  Thing code = logb->Ref(pos + COMPILE_LOG_CODE);
	  cout << "depth " << depth << " code= " << ToString(code) << endl;
	}
      }
    }
  }
}

void Vinterpreter::LoadFile(string fn, bool verbose, uint64 mode) {
  // cout << "Loading file: " << fn << endl;
  if (loaded_files_ % fn) {
    cout << "Already loaded" << endl;
    return;
  }
  loaded_files_.insert(fn);
  ifstream input(fn.c_str());
  ExecuteStream(input, verbose, mode);
  // cout << "Loaded" << endl;
}

void Vinterpreter::ExecuteStream(istream &input, bool verbose, uint64 mode) {
  // CHECK(false);
  // cout << "::ExecuteStream\n";
  while (1) {
    if (&input == &cin) cout << "IN> ";
    Thing o = ReadThing(a_, input);
    if (o.IsNot()) break;
    if (verbose) cout << "code: " << o << endl;
    // Is this a load command? WORKING
    if ((o.IsArray()) && 
	(o.GetBox()->ArraySize() == 2) &&
	(o.GetBox()->Ref(0) == LOAD)) {
      Thing fn = o.GetBox()->Ref(1);
      if (fn.IsString()) {
	string fns = StringToCPPString(fn);
	LoadFile(fns, verbose, mode);
      }
    } else {
      int64 start_time = TimeNS();
      // cout << "About to run code " << o << endl;
      Thing result = SafeExecute(o, (int64) 1e10, mode, NIL);
      if (result.IsNot()) {
	cout << "code did not return" << endl;
	cout << o << endl;
      }
      if (result.Is() && verbose) {
	cout << "returned: " << result << endl;
	cout << "#Time(ns): " 
	     << Delimit(TimeNS() - start_time) << endl;
      }
    }
  }
}

void Vinterpreter::SaveState(InterpreterState * state) {
    state->mode_ = mode_;
    state->ip_ = ip_;
    state->stack_top_ = stack_top_;
    state->debug_stack_top_ = debug_stack_top_;
    state->code_stack_top_ = code_stack_top_;
    state->array_stack_size_ = array_stack_.size();
    state->run_global_ = run_global_;
  }

void Vinterpreter::RestoreState(const InterpreterState & state) {
  mode_ = state.mode_;
  JumpTo(state.ip_);
  stack_top_ = state.stack_top_;
  debug_stack_top_ = state.debug_stack_top_;
  code_stack_top_ = state.code_stack_top_;
  array_stack_.resize(state.array_stack_size_);		 
  run_global_ = state.run_global_;    
}

void Vinterpreter::PrintHandlerStack() { 
    for (int i=0; i<handler_stack_top_ - handler_stack_; i++) {
      cout << "HandlerStack " << i << 
	" clock_limit_ = " << handler_stack_[i].clock_limit_ << endl;
    }
  }

void Vinterpreter::PrintStack() {
    for (int i=0; i<stack_top_ - stack_ ; i++) {
      cout << "Stack " << i << " " << stack_[i] << endl;
    }
  }

void Vinterpreter::RollBackHandlerStack(HandlerFrame *p) {
    CHECK(p < handler_stack_top_);
    handler_stack_top_ = p;
    RestoreState(p->return_state_);
}

void Vinterpreter::PushHandlerFrame
(int64 clock_limit, 
 Thing exceptions, 
 Thing type) {
    HandlerFrame & xframe = *(handler_stack_top_++);
    SaveState(&(xframe.return_state_));
    xframe.clock_limit_ = clock_limit;
    xframe.exceptions_ = exceptions;
    xframe.type_ = type;
  }

void Vinterpreter::CatchWithHandler(HandlerFrame *p) {
  CHECK(p < handler_stack_top_);
  if (p->type_ == SAFEEXECUTE) {
    safe_execute_die_ = true;
    return;
    // throw SafeExecuteException();
  }
  RollBackHandlerStack(p);
  *(stack_top_++) = NIL;
}

void Vinterpreter::FailTimeLimit() {
  NoFunctionCache();
  NoProgramCache();
  HandlerFrame *p = handler_stack_top_-1;
  while ( (p->type_ != SAFEEXECUTE) && (p[-1].clock_limit_ <= clock_.Get()) )
    p--;
  CatchWithHandler(p);
}

void Vinterpreter::Throw(Thing x, string message) {
  HandlerFrame * p = handler_stack_top_ - 1;
  for (; true; p--) {
    if (p->ExceptionMatches(x)) {
      if (p->type_ == DEBUG) break;
      CatchWithHandler(p);
      return;
    }
    if (p->type_ == SAFEEXECUTE) break;
  }
  // type_ is either DEBUG or SAFEEXECUTE
  cout << endl;
  if (p->type_ == DEBUG) cout << p->type_ << " ";
  cout << x << " " << message << endl;
  Debug();
  CHECK(false);
}

int interpret_main() {
  InitAllocator();
  srand(time(0));
  InitInterpret();
  Vinterpreter tinterp;
  ThreadAllocator ta;
  tinterp.a_ = &ta;
  tinterp.LoadFile("library", false, kNoSystemMode);
  tinterp.ExecuteStream(cin, true, kNoSystemMode);
  ta.ClearLocalBlock();
  return 0;
}

// returns success
bool Vinterpreter::SetGlobal(Thing key, Thing value) {
  bool failure = false;
  key = a_->Globalize(key);
  value = a_->Globalize(value);
  pthread_mutex_lock(&G_LOCK);
  if (G_INTERP->globals_ % key) failure = true;
  else G_INTERP->globals_[key] = value;
  pthread_mutex_unlock(&G_LOCK);
  return !failure;
}


// int main(int argc, char ** argv) {  return interpret_main(); }
